/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-02-24
 * Time: 21:04
 */
public class HashBuck {
    static class Node{
        public int key;
        public int value;//我们这里以整形value为例，如果需要其他类型可以自行修改
        public Node next;

        public Node(int key,int val){
            this.key=key;
            this.value=val;
        }
    }

    public Node[] array;
    public int usedSize;

    public HashBuck(){
        this.array=new Node[10];
    }

    public static final double DEFAULT_LOAD_FACTOR=0.75;
    //一般负载因子不可以改变，所以这里用 static final

    //put函数
    public void put(int key,int val){
        //1.找到key所在位置
        int index=key%this.array.length;

        //2.遍历这个下标的链表，看是不是有相同的key,如果有，就要更新value
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                cur.value=val;
                return;
            }
            cur=cur.next;
        }
        //3.走到这里，说明没有key这个元素,我们这里用头插法(如果你想，尾插也可以的，后面用的时候没有影响)
        Node node=new Node(key, val);
        node.next=array[index];
        array[index]=node;
        this.usedSize++;
        //4.插入元素成功后，检查当前散列表的负载因子
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            resize();
        }
    }
    //负载因子
    private double loadFactor(){
        return 1.0*this.usedSize/array.length;//1.0*是为了变成double型
    }

    //扩容
    private void resize(){
        //扩容也不仅仅是扩容，比如原先数组大小是10
        //我们扩容到20，那原先11本来是放在1号下标位置，现在要放到11号位置了
        //所以，每次扩容，我们都需要再重新哈希一遍（所有数据重新放入表内）
        Node[] newArray=new Node[array.length*2];
        for(int i=0;i<array.length;i++){
            Node cur=array[i];
            while(cur!=null){
                int index=cur.key% newArray.length;//获取重新哈希的index下标
                //下面就是需要把cur这个节点，以头插/尾插的形式插入新数组的index下标
                Node curNext=cur.next;
                cur.next=newArray[index];//先绑定前面
                newArray[index]=cur;
                cur=curNext;
            }
        }
        array=newArray;
    }

    //根据key获取value
    public int get(int key){
        //1.找到key所在位置
        int index=key%this.array.length;

        //2.遍历这个下标的链表，看是不是有相同的key,如果有，就要更新value
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;
    }

    public static void main(String[] args) {
        HashBuck hashBuck=new HashBuck();
        hashBuck.put(1,1);
        hashBuck.put(21,3);
        hashBuck.put(4,4);
        hashBuck.put(26,7);
        hashBuck.put(2,2);
        hashBuck.put(90,24);
        //测试：
        //通过key找到value
        System.out.println(hashBuck.get(21));//打印3

        //扩容
    }
}

